﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Security.Permissions;
using System.Xml.Serialization;
using Jeelu.Interface.Tree;

namespace Jeelu.Collections.Tree
{
    [Serializable]
    public class NodeTree<T> : INode<T>, ITree<T>, ISerializable
    {
        protected static readonly object _XmlAdapterTag = new object();
        private static readonly object _ValidateEventKey = new object();
        private static readonly object _ClearingEventKey = new object();
        private static readonly object _ClearedEventKey = new object();
        private static readonly object _SettingEventKey = new object();
        private static readonly object _SetDoneEventKey = new object();
        private static readonly object _InsertingEventKey = new object();
        private static readonly object _InsertedEventKey = new object();
        private static readonly object _CuttingEventKey = new object();
        private static readonly object _CutDoneEventKey = new object();
        private static readonly object _CopyingEventKey = new object();
        private static readonly object _CopiedEventKey = new object();
        private static readonly object _DeepCopyingEventKey = new object();
        private static readonly object _DeepCopiedEventKey = new object();

        private NodeTree<T> _Child;
        private T _Data;
        private EventHandlerList _EventHandlerList;
        private NodeTree<T> _Next;

        private NodeTree<T> _Parent;
        private NodeTree<T> _Previous;

        protected NodeTree()
        {
        }

        protected NodeTree(SerializationInfo info, StreamingContext context)
        {
            int iVersion = info.GetInt32("NodeTreeVersion");
            if (iVersion != 1) throw new SerializationException("Unknown version");

            _Data = (T) info.GetValue("Data", typeof (T));
            _Parent = (NodeTree<T>) info.GetValue("Parent", typeof (NodeTree<T>));
            _Previous = (NodeTree<T>) info.GetValue("Previous", typeof (NodeTree<T>));
            _Next = (NodeTree<T>) info.GetValue("Next", typeof (NodeTree<T>));
            _Child = (NodeTree<T>) info.GetValue("Child", typeof (NodeTree<T>));
        }

        protected virtual RootObject GetRootObject
        {
            get { return (RootObject) Root; }
        }

        protected virtual int Version
        {
            get
            {
                INode<T> root = Root;
                if (!root.IsTree)
                    throw new InvalidOperationException("This is not a Tree");
                return GetNodeTree(root).Version;
            }
            set
            {
                INode<T> root = Root;
                if (!root.IsTree)
                    throw new InvalidOperationException("This is not a Tree");
                GetNodeTree(root).Version = value;
            }
        }

        public virtual bool IsReadOnly
        {
            get { return false; }
        }

        protected EventHandlerList EventHandlerList
        {
            get { return _EventHandlerList; }
        }

        protected static object ValidateEventKey
        {
            get { return _ValidateEventKey; }
        }

        protected static object ClearingEventKey
        {
            get { return _ClearingEventKey; }
        }

        protected static object ClearedEventKey
        {
            get { return _ClearedEventKey; }
        }

        protected static object SettingEventKey
        {
            get { return _SettingEventKey; }
        }

        protected static object SetDoneEventKey
        {
            get { return _SetDoneEventKey; }
        }

        protected static object InsertingEventKey
        {
            get { return _InsertingEventKey; }
        }

        protected static object InsertedEventKey
        {
            get { return _InsertedEventKey; }
        }

        protected static object CuttingEventKey
        {
            get { return _CuttingEventKey; }
        }

        protected static object CutDoneEventKey
        {
            get { return _CutDoneEventKey; }
        }

        protected static object CopyingEventKey
        {
            get { return _CopyingEventKey; }
        }

        protected static object CopiedEventKey
        {
            get { return _CopiedEventKey; }
        }

        protected static object DeepCopyingEventKey
        {
            get { return _DeepCopyingEventKey; }
        }

        protected static object DeepCopiedEventKey
        {
            get { return _DeepCopiedEventKey; }
        }

        #region INode<T> Members

        public void Dispose()
        {
            Dispose(true);

            GC.SuppressFinalize(this);
        }

        public virtual string ToStringRecursive()
        {
            return All.Nodes.Cast<NodeTree<T>>().Aggregate(String.Empty, (current, node) => current + (new String('\t', node.Depth) + node + Environment.NewLine));
        }

        public virtual int Depth
        {
            get
            {
                int i = -1;
                for (INode<T> node = this; !node.IsRoot; node = node.Parent) 
                    i++;
                return i;
            }
        }

        public virtual int BranchIndex
        {
            get
            {
                int i = -1;
                for (INode<T> node = this; node != null; node = node.Previous) 
                    i++;
                return i;
            }
        }

        public virtual int BranchCount
        {
            get
            {
                int i = 0;
                for (INode<T> node = First; node != null; node = node.Next) 
                    i++;
                return i;
            }
        }

        public T Data
        {
            get { return _Data; }

            set
            {
                if (IsRoot) 
                    throw new InvalidOperationException("This is a Root");
                OnSetting(this, value);
                _Data = value;
                OnSetDone(this, value);
            }
        }

        public INode<T> Parent
        {
            get { return _Parent; }
        }

        public INode<T> Previous
        {
            get { return _Previous; }
        }

        public INode<T> Next
        {
            get { return _Next; }
        }

        public INode<T> Child
        {
            get { return _Child; }
        }

        public ITree<T> Tree
        {
            get { return (ITree<T>) Root; }
        }

        public INode<T> Root
        {
            get
            {
                INode<T> node = this;
                while (node.Parent != null)
                    node = node.Parent;
                return node;
            }
        }

        public INode<T> Top
        {
            get
            {
                if (!Root.IsTree) 
                    throw new InvalidOperationException("This is not a tree");
                if (IsRoot) 
                    return null;

                INode<T> node = this;
                while (node.Parent.Parent != null)
                    node = node.Parent;
                return node;
            }
        }

        public INode<T> First
        {
            get
            {
                INode<T> node = this;
                while (node.Previous != null)
                    node = node.Previous;
                return node;
            }
        }

        public INode<T> Last
        {
            get
            {
                INode<T> node = this;
                while (node.Next != null)
                    node = node.Next;
                return node;
            }
        }

        public INode<T> LastChild
        {
            get
            {
                if (Child == null) 
                    return null;
                return Child.Last;
            }
        }

        public bool HasPrevious
        {
            get { return Previous != null; }
        }

        public bool HasNext
        {
            get { return Next != null; }
        }

        public bool HasChild
        {
            get { return Child != null; }
        }

        public bool IsFirst
        {
            get { return Previous == null; }
        }

        public bool IsLast
        {
            get { return Next == null; }
        }

        public bool IsTree
        {
            get
            {
                if (!IsRoot) 
                    return false;
                return this is RootObject;
            }
        }

        public bool IsRoot
        {
            get
            {
                bool b = (Parent == null);

                if (b)
                {
                    Debug.Assert(Previous == null);
                    Debug.Assert(Next == null);
                }

                return b;
            }
        }

        public bool HasParent
        {
            get
            {
                if (IsRoot) return false;
                return Parent.Parent != null;
            }
        }

        public bool IsTop
        {
            get
            {
                if (IsRoot) return false;
                return Parent.Parent == null;
            }
        }

        public virtual INode<T> this[T item]
        {
            get
            {
                if (!Root.IsTree)
                    throw new InvalidOperationException("This is not a tree");
                IEqualityComparer<T> comparer = DataComparer;
                return All.Nodes.FirstOrDefault(n => comparer.Equals(n.Data, item));
            }
        }

        public virtual bool Contains(INode<T> item)
        {
            if (!Root.IsTree) 
                throw new InvalidOperationException("This is not a tree");
            return All.Nodes.Contains(item);
        }

        public virtual bool Contains(T item)
        {
            if (!Root.IsTree) 
                throw new InvalidOperationException("This is not a tree");
            return All.Values.Contains(item);
        }

        public INode<T> InsertPrevious(T o)
        {
            if (IsRoot) 
                throw new InvalidOperationException("This is a Root");
            if (!Root.IsTree) 
                throw new InvalidOperationException("This is not a tree");
            NodeTree<T> newNode = CreateNode();
            newNode._Data = o;
            InsertPreviousCore(newNode);
            return newNode;
        }

        public INode<T> InsertNext(T o)
        {
            if (IsRoot) 
                throw new InvalidOperationException("This is a Root");
            if (!Root.IsTree) 
                throw new InvalidOperationException("This is not a tree");

            NodeTree<T> newNode = CreateNode();
            newNode._Data = o;
            InsertNextCore(newNode);
            return newNode;
        }

        public INode<T> InsertChild(T o)
        {
            if (!Root.IsTree) 
                throw new InvalidOperationException("This is not a tree");

            NodeTree<T> newNode = CreateNode();
            newNode._Data = o;

            InsertChildCore(newNode);

            return newNode;
        }

        public INode<T> Add(T o)
        {
            if (IsRoot) 
                throw new InvalidOperationException("This is a Root");
            if (!Root.IsTree) 
                throw new InvalidOperationException("This is not a tree");

            return Last.InsertNext(o);
        }

        public INode<T> AddChild(T o)
        {
            if (!Root.IsTree) 
                throw new InvalidOperationException("This is not a tree");

            if (Child == null)
                return InsertChild(o);
            return Child.Add(o);
        }

        public void InsertPrevious(ITree<T> tree)
        {
            if (IsRoot) throw new InvalidOperationException("This is a Root");
            if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

            NodeTree<T> newTree = GetNodeTree(tree);

            if (!newTree.IsRoot) throw new ArgumentException("Tree is not a Root");
            if (!newTree.IsTree) throw new ArgumentException("Tree is not a tree");

            for (INode<T> n = newTree.Child; n != null; n = n.Next)
            {
                NodeTree<T> node = GetNodeTree(n);
                NodeTree<T> copy = node.CopyCore();
                InsertPreviousCore(copy);
            }
        }

        public void InsertNext(ITree<T> tree)
        {
            if (IsRoot) throw new InvalidOperationException("This is a Root");
            if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

            NodeTree<T> newTree = GetNodeTree(tree);

            if (!newTree.IsRoot) throw new ArgumentException("Tree is not a Root");
            if (!newTree.IsTree) throw new ArgumentException("Tree is not a tree");

            for (INode<T> n = newTree.LastChild; n != null; n = n.Previous)
            {
                NodeTree<T> node = GetNodeTree(n);
                NodeTree<T> copy = node.CopyCore();
                InsertNextCore(copy);
            }
        }

        public void InsertChild(ITree<T> tree)
        {
            if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

            NodeTree<T> newTree = GetNodeTree(tree);

            if (!newTree.IsRoot) throw new ArgumentException("Tree is not a Root");
            if (!newTree.IsTree) throw new ArgumentException("Tree is not a tree");

            for (INode<T> n = newTree.LastChild; n != null; n = n.Previous)
            {
                NodeTree<T> node = GetNodeTree(n);
                NodeTree<T> copy = node.CopyCore();
                InsertChildCore(copy);
            }
        }

        public void Add(ITree<T> tree)
        {
            if (IsRoot) throw new InvalidOperationException("This is a Root");
            if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

            Last.InsertNext(tree);
        }

        public void AddChild(ITree<T> tree)
        {
            if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

            if (Child == null)
                InsertChild(tree);
            else
                Child.Add(tree);
        }

        public ITree<T> Cut(T o)
        {
            if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

            INode<T> n = this[o];
            if (n == null) return null;
            return n.Cut();
        }

        public ITree<T> Copy(T o)
        {
            if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

            INode<T> n = this[o];
            if (n == null) return null;
            return n.Copy();
        }

        public ITree<T> DeepCopy(T o)
        {
            if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

            INode<T> n = this[o];
            if (n == null) return null;
            return n.DeepCopy();
        }

        public bool Remove(T o)
        {
            if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

            INode<T> n = this[o];
            if (n == null) return false;

            n.Remove();
            return true;
        }

        public ITree<T> Cut()
        {
            if (IsRoot) throw new InvalidOperationException("This is a Root");
            if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

            NodeTree<T> node = CutCore();

            return BoxInTree(node);
        }

        public ITree<T> Copy()
        {
            if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

            if (IsTree)
            {
                NodeTree<T> newTree = CopyCore();
                return newTree;
            }
            else
            {
                NodeTree<T> newNode = CopyCore();
                return BoxInTree(newNode);
            }
        }

        public ITree<T> DeepCopy()
        {
            if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

            if (IsTree)
            {
                NodeTree<T> newTree = DeepCopyCore();
                return newTree;
            }
            else
            {
                NodeTree<T> newNode = DeepCopyCore();
                return BoxInTree(newNode);
            }
        }

        public void Remove()
        {
            if (IsRoot) 
                throw new InvalidOperationException("This is a Root");
            if (!Root.IsTree) 
                throw new InvalidOperationException("This is not a tree");

            RemoveCore();
        }

        public bool CanMoveToParent
        {
            get
            {
                if (IsRoot)
                    return false;
                if (IsTop) 
                    return false;
                return true;
            }
        }

        public bool CanMoveToPrevious
        {
            get
            {
                if (IsRoot) 
                    return false;
                if (IsFirst) 
                    return false;
                return true;
            }
        }

        public bool CanMoveToNext
        {
            get
            {
                if (IsRoot) 
                    return false;
                if (IsLast) 
                    return false;
                return true;
            }
        }

        public bool CanMoveToChild
        {
            get
            {
                if (IsRoot) 
                    return false;
                if (IsFirst) 
                    return false;
                return true;
            }
        }

        public bool CanMoveToFirst
        {
            get
            {
                if (IsRoot) return false;
                if (IsFirst) return false;

                return true;
            }
        }

        public bool CanMoveToLast
        {
            get
            {
                if (IsRoot) return false;
                if (IsLast) return false;

                return true;
            }
        }

        public void MoveToParent()
        {
            if (!CanMoveToParent) throw new InvalidOperationException("Cannot move to Parent");

            NodeTree<T> parentNode = GetNodeTree(Parent);

            NodeTree<T> thisNode = CutCore();

            parentNode.InsertNextCore(thisNode);
        }

        public void MoveToPrevious()
        {
            if (!CanMoveToPrevious) throw new InvalidOperationException("Cannot move to Previous");

            NodeTree<T> previousNode = GetNodeTree(Previous);

            NodeTree<T> thisNode = CutCore();

            previousNode.InsertPreviousCore(thisNode);
        }

        public void MoveToNext()
        {
            if (!CanMoveToNext) throw new InvalidOperationException("Cannot move to Next");

            NodeTree<T> nextNode = GetNodeTree(Next);

            NodeTree<T> thisNode = CutCore();

            nextNode.InsertNextCore(thisNode);
        }

        public void MoveToChild()
        {
            if (!CanMoveToChild) throw new InvalidOperationException("Cannot move to Child");

            NodeTree<T> previousNode = GetNodeTree(Previous);

            NodeTree<T> thisNode = CutCore();

            previousNode.AddChildCore(thisNode);
        }

        public void MoveToFirst()
        {
            if (!CanMoveToFirst) throw new InvalidOperationException("Cannot move to first");

            NodeTree<T> firstNode = GetNodeTree(First);

            NodeTree<T> thisNode = CutCore();

            firstNode.InsertPreviousCore(thisNode);
        }

        public void MoveToLast()
        {
            if (!CanMoveToLast) throw new InvalidOperationException("Cannot move to last");

            NodeTree<T> lastNode = GetNodeTree(Last);

            NodeTree<T> thisNode = CutCore();

            lastNode.InsertNextCore(thisNode);
        }

        public virtual IEnumerableCollection<INode<T>> Nodes
        {
            get { return All.Nodes; }
        }

        public virtual IEnumerableCollection<T> Values
        {
            get { return All.Values; }
        }

        public IEnumerableCollectionPair<T> All
        {
            get { return new AllEnumerator(this); }
        }

        public IEnumerableCollectionPair<T> AllChildren
        {
            get { return new AllChildrenEnumerator(this); }
        }

        public IEnumerableCollectionPair<T> DirectChildren
        {
            get { return new DirectChildrenEnumerator(this); }
        }

        public IEnumerableCollectionPair<T> DirectChildrenInReverse
        {
            get { return new DirectChildrenInReverseEnumerator(this); }
        }

        public int DirectChildCount
        {
            get
            {
                int i = 0;

                for (INode<T> n = Child; n != null; n = n.Next) i++;

                return i;
            }
        }

        public virtual int Count
        {
            get
            {
                int i = IsRoot ? 0 : 1;

                for (INode<T> n = Child; n != null; n = n.Next)
                    i += n.Count;

                return i;
            }
        }

        public event EventHandler<NodeTreeDataEventArgs<T>> Validate
        {
            add { GetCreateEventHandlerList().AddHandler(ValidateEventKey, value); }

            remove { GetCreateEventHandlerList().RemoveHandler(ValidateEventKey, value); }
        }

        public event EventHandler<NodeTreeDataEventArgs<T>> Setting
        {
            add { GetCreateEventHandlerList().AddHandler(SettingEventKey, value); }

            remove { GetCreateEventHandlerList().RemoveHandler(SettingEventKey, value); }
        }

        public event EventHandler<NodeTreeDataEventArgs<T>> SetDone
        {
            add { GetCreateEventHandlerList().AddHandler(SetDoneEventKey, value); }

            remove { GetCreateEventHandlerList().RemoveHandler(SetDoneEventKey, value); }
        }

        public event EventHandler<NodeTreeInsertEventArgs<T>> Inserting
        {
            add { GetCreateEventHandlerList().AddHandler(InsertingEventKey, value); }

            remove { GetCreateEventHandlerList().RemoveHandler(InsertingEventKey, value); }
        }

        public event EventHandler<NodeTreeInsertEventArgs<T>> Inserted
        {
            add { GetCreateEventHandlerList().AddHandler(InsertedEventKey, value); }

            remove { GetCreateEventHandlerList().RemoveHandler(InsertedEventKey, value); }
        }

        public event EventHandler Cutting
        {
            add { GetCreateEventHandlerList().AddHandler(CuttingEventKey, value); }

            remove { GetCreateEventHandlerList().RemoveHandler(CuttingEventKey, value); }
        }

        public event EventHandler CutDone
        {
            add { GetCreateEventHandlerList().AddHandler(CutDoneEventKey, value); }

            remove { GetCreateEventHandlerList().RemoveHandler(CutDoneEventKey, value); }
        }

        public event EventHandler<NodeTreeNodeEventArgs<T>> Copying
        {
            add { GetCreateEventHandlerList().AddHandler(CopyingEventKey, value); }

            remove { GetCreateEventHandlerList().RemoveHandler(CopyingEventKey, value); }
        }

        public event EventHandler<NodeTreeNodeEventArgs<T>> Copied
        {
            add { GetCreateEventHandlerList().AddHandler(CopiedEventKey, value); }

            remove { GetCreateEventHandlerList().RemoveHandler(CopiedEventKey, value); }
        }

        public event EventHandler<NodeTreeNodeEventArgs<T>> DeepCopying
        {
            add { GetCreateEventHandlerList().AddHandler(DeepCopyingEventKey, value); }

            remove { GetCreateEventHandlerList().RemoveHandler(DeepCopyingEventKey, value); }
        }

        public event EventHandler<NodeTreeNodeEventArgs<T>> DeepCopied
        {
            add { GetCreateEventHandlerList().AddHandler(DeepCopiedEventKey, value); }

            remove { GetCreateEventHandlerList().RemoveHandler(DeepCopiedEventKey, value); }
        }

        #endregion

        #region ISerializable Members

        [SecurityPermission(SecurityAction.Demand, SerializationFormatter = true)]
        public virtual void GetObjectData(SerializationInfo info, StreamingContext context)
        {
            info.AddValue("NodeTreeVersion", 1);
            info.AddValue("Data", _Data);
            info.AddValue("Parent", _Parent);
            info.AddValue("Previous", _Previous);
            info.AddValue("Next", _Next);
            info.AddValue("Child", _Child);
        }

        #endregion

        #region ITree<T> Members

        public virtual IEqualityComparer<T> DataComparer
        {
            get
            {
                if (!Root.IsTree) throw new InvalidOperationException("This is not a Tree");

                return GetRootObject.DataComparer;
            }

            set
            {
                if (!Root.IsTree) throw new InvalidOperationException("This is not a Tree");

                GetRootObject.DataComparer = value;
            }
        }

        public virtual void XmlSerialize(Stream stream)
        {
            XmlSerializer xmlSerializer;

            try
            {
                xmlSerializer = new XmlSerializer(typeof (TreeXmlSerializationAdapter));
            }
            catch (Exception x)
            {
                Debug.Assert(x == null); // false
                throw;
            }

            try
            {
                xmlSerializer.Serialize(stream, new TreeXmlSerializationAdapter(_XmlAdapterTag, this));
            }
            catch (Exception x)
            {
                Debug.Assert(x == null); // false
                throw;
            }
        }

        public virtual Type DataType
        {
            get { return typeof (T); }
        }

        public void Clear()
        {
            if (!IsRoot) throw new InvalidOperationException("This is not a Root");
            if (!IsTree) throw new InvalidOperationException("This is not a tree");

            OnClearing(this);

            _Child = null;

            OnCleared(this);
        }

        public event EventHandler Clearing
        {
            add { GetCreateEventHandlerList().AddHandler(ClearingEventKey, value); }
            remove { GetCreateEventHandlerList().RemoveHandler(ClearingEventKey, value); }
        }

        public event EventHandler Cleared
        {
            add { GetCreateEventHandlerList().AddHandler(ClearedEventKey, value); }
            remove { GetCreateEventHandlerList().RemoveHandler(ClearedEventKey, value); }
        }

        #endregion

        ~NodeTree()
        {
            Dispose(false);
        }

        protected virtual void Dispose(bool disposing)
        {
            if (disposing)
            {
                if (_EventHandlerList != null)
                    _EventHandlerList.Dispose();
            }
        }

        public static ITree<T> NewTree()
        {
            return new RootObject();
        }

        public static ITree<T> NewTree(IEqualityComparer<T> dataComparer)
        {
            return new RootObject(dataComparer);
        }

        protected static INode<T> NewNode()
        {
            return new NodeTree<T>();
        }

        protected virtual NodeTree<T> CreateTree()
        {
            return new RootObject();
        }

        protected virtual NodeTree<T> CreateNode()
        {
            return new NodeTree<T>();
        }

        public override string ToString()
        {
            T data = Data;
            if (data == null)
                return String.Empty;
            return data.ToString();
        }

        [ReflectionPermission(SecurityAction.Demand, Unrestricted = true)]
        protected virtual T DeepCopyData(T data)
        {
            if (data == null)
            {
                Debug.Assert(true);
                return default(T);
            }

            // IDeepCopy
            var deepCopy = data as IDeepCopy;
            if (deepCopy != null) return (T) deepCopy.CreateDeepCopy();

            // ICloneable
            var cloneable = data as ICloneable;
            if (cloneable != null) return (T) cloneable.Clone();

            // Copy constructor
            ConstructorInfo ctor = data.GetType().GetConstructor(
                BindingFlags.Instance | BindingFlags.Public,
                null, new[] {typeof (T)}, null);
            if (ctor != null)
                return (T) ctor.Invoke(new object[] {data});
            return data;
        }

        protected bool HasChanged(int version)
        {
            return (Version != version);
        }

        protected void IncrementVersion()
        {
            INode<T> root = Root;

            if (!root.IsTree)
                throw new InvalidOperationException("This is not a Tree");

            GetNodeTree(root).Version++;
        }

        public static ITree<T> XmlDeserialize(Stream stream)
        {
            XmlSerializer xmlSerializer;

            try
            {
                xmlSerializer = new XmlSerializer(typeof (TreeXmlSerializationAdapter));
            }
            catch (Exception x)
            {
                Debug.Assert(x == null); // false
                throw;
            }

            object o;

            try
            {
                o = xmlSerializer.Deserialize(stream);
            }
            catch (Exception x)
            {
                Debug.Assert(x == null); // false
                throw;
            }

            var adapter = (TreeXmlSerializationAdapter) o;

            ITree<T> tree = adapter.Tree;

            return tree;
        }

        protected virtual void InsertPreviousCore(INode<T> newINode)
        {
            if (IsRoot) throw new InvalidOperationException("This is a Root");
            if (!newINode.IsRoot) throw new ArgumentException("Node is not a Root");
            if (newINode.IsTree) throw new ArgumentException("Node is a tree");

            IncrementVersion();

            OnInserting(this, NodeTreeInsertOperation.Previous, newINode);

            NodeTree<T> newNode = GetNodeTree(newINode);

            newNode._Parent = _Parent;
            newNode._Previous = _Previous;
            newNode._Next = this;
            _Previous = newNode;

            if (newNode.Previous != null)
            {
                NodeTree<T> Previous = GetNodeTree(newNode.Previous);
                Previous._Next = newNode;
            }
            else // this is a first node
            {
                NodeTree<T> Parent = GetNodeTree(newNode.Parent);
                Parent._Child = newNode;
            }

            OnInserted(this, NodeTreeInsertOperation.Previous, newINode);
        }

        protected virtual void InsertNextCore(INode<T> newINode)
        {
            if (IsRoot) throw new InvalidOperationException("This is a Root");
            if (!newINode.IsRoot) throw new ArgumentException("Node is not a Root");
            if (newINode.IsTree) throw new ArgumentException("Node is a tree");

            IncrementVersion();

            OnInserting(this, NodeTreeInsertOperation.Next, newINode);

            NodeTree<T> newNode = GetNodeTree(newINode);

            newNode._Parent = _Parent;
            newNode._Previous = this;
            newNode._Next = _Next;
            _Next = newNode;

            if (newNode.Next != null)
            {
                NodeTree<T> Next = GetNodeTree(newNode.Next);
                Next._Previous = newNode;
            }

            OnInserted(this, NodeTreeInsertOperation.Next, newINode);
        }

        protected virtual void InsertChildCore(INode<T> newINode)
        {
            if (!newINode.IsRoot) throw new ArgumentException("Node is not a Root");
            if (newINode.IsTree) throw new ArgumentException("Node is a tree");

            IncrementVersion();

            OnInserting(this, NodeTreeInsertOperation.Child, newINode);

            NodeTree<T> newNode = GetNodeTree(newINode);

            newNode._Parent = this;
            newNode._Next = _Child;
            _Child = newNode;

            if (newNode.Next != null)
            {
                NodeTree<T> Next = GetNodeTree(newNode.Next);
                Next._Previous = newNode;
            }

            OnInserted(this, NodeTreeInsertOperation.Child, newINode);
        }

        protected virtual void AddCore(INode<T> newINode)
        {
            if (IsRoot) throw new InvalidOperationException("This is a Root");

            NodeTree<T> lastNode = GetNodeTree(Last);

            lastNode.InsertNextCore(newINode);
        }

        protected virtual void AddChildCore(INode<T> newINode)
        {
            if (Child == null)
                InsertChildCore(newINode);
            else
            {
                NodeTree<T> childNode = GetNodeTree(Child);

                childNode.AddCore(newINode);
            }
        }

        private NodeTree<T> BoxInTree(NodeTree<T> node)
        {
            if (!node.IsRoot)
                throw new ArgumentException("Node is not a Root");
            if (node.IsTree)
                throw new ArgumentException("Node is a tree");

            NodeTree<T> tree = CreateTree();
            tree.AddChildCore(node);

            return tree;
        }

        protected virtual NodeTree<T> CutCore()
        {
            if (IsRoot) throw new InvalidOperationException("This is a Root");

            IncrementVersion();

            OnCutting(this);

            INode<T> oldRoot = Root;

            if (_Next != null)
                _Next._Previous = _Previous;

            if (Previous != null)
                _Previous._Next = _Next;
            else // this is a first node
            {
                Debug.Assert(Parent.Child == this);
                _Parent._Child = _Next;
                Debug.Assert(Next == null || Next.Previous == null);
            }

            _Parent = null;
            _Previous = null;
            _Next = null;

            OnCutDone(oldRoot, this);

            return this;
        }

        protected virtual NodeTree<T> CopyCore()
        {
            if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");
            if (IsRoot && !IsTree) throw new InvalidOperationException("This is a Root");

            if (IsTree)
            {
                NodeTree<T> NewTree = CreateTree();

                OnCopying(this, NewTree);

                CopyChildNodes(this, NewTree, false);

                OnCopied(this, NewTree);

                return NewTree;
            }
            else
            {
                NodeTree<T> NewNode = CreateNode();

                NewNode._Data = Data;

                OnCopying(this, NewNode);

                CopyChildNodes(this, NewNode, false);

                OnCopied(this, NewNode);

                return NewNode;
            }
        }

        protected virtual NodeTree<T> DeepCopyCore()
        {
            if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");
            if (IsRoot && !IsTree) throw new InvalidOperationException("This is a Root");

            if (IsTree)
            {
                NodeTree<T> NewTree = CreateTree();

                OnCopying(this, NewTree);

                CopyChildNodes(this, NewTree, true);

                OnCopied(this, NewTree);

                return NewTree;
            }
            else
            {
                NodeTree<T> NewNode = CreateNode();

                NewNode._Data = DeepCopyData(Data);

                OnDeepCopying(this, NewNode);

                CopyChildNodes(this, NewNode, true);

                OnDeepCopied(this, NewNode);

                return NewNode;
            }
        }

        private void CopyChildNodes(INode<T> oldNode, NodeTree<T> newNode, bool bDeepCopy)
        {
            NodeTree<T> previousNewChildNode = null;

            for (INode<T> oldChildNode = oldNode.Child; oldChildNode != null; oldChildNode = oldChildNode.Next)
            {
                NodeTree<T> newChildNode = CreateNode();

                if (!bDeepCopy)
                    newChildNode._Data = oldChildNode.Data;
                else
                    newChildNode._Data = DeepCopyData(oldChildNode.Data);

                //				if ( ! bDeepCopy )
                //					OnCopying( oldChildNode, newChildNode );
                //				else
                //					OnDeepCopying( oldChildNode, newChildNode );

                if (oldChildNode.Previous == null) newNode._Child = newChildNode;

                newChildNode._Parent = newNode;
                newChildNode._Previous = previousNewChildNode;
                if (previousNewChildNode != null) previousNewChildNode._Next = newChildNode;

                //				if ( ! bDeepCopy )
                //					OnCopied( oldChildNode, newChildNode );
                //				else
                //					OnDeepCopied( oldChildNode, newChildNode );

                CopyChildNodes(oldChildNode, newChildNode, bDeepCopy);

                previousNewChildNode = newChildNode;
            }
        }

        protected virtual void RemoveCore()
        {
            if (IsRoot)
                throw new InvalidOperationException("This is a Root");
            CutCore();
        }

        protected static NodeTree<T> GetNodeTree(ITree<T> tree)
        {
            if (tree == null)
                throw new ArgumentNullException("Tree is null");
            return (NodeTree<T>) tree;
        }

        protected static NodeTree<T> GetNodeTree(INode<T> node)
        {
            if (node == null)
                throw new ArgumentNullException("Node is null");
            return (NodeTree<T>) node; // can throw an InvalidCastException.
        }

        protected EventHandlerList GetCreateEventHandlerList()
        {
            return _EventHandlerList ?? (_EventHandlerList = new EventHandlerList());
        }

        #region EventHandler ...

        protected virtual void OnValidate(INode<T> node, T data)
        {
            if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");
            if (data is INode<T>) throw new ArgumentException("Object is a node");

            if ((!typeof (T).IsClass) || data != null)
                if (!DataType.IsInstanceOfType(data))
                    throw new ArgumentException("Object is not a " + DataType.Name);

            if (_EventHandlerList != null)
            {
                var e = (EventHandler<NodeTreeDataEventArgs<T>>) _EventHandlerList[ValidateEventKey];
                if (e != null) e(node, new NodeTreeDataEventArgs<T>(data));
            }

            if (!IsRoot) GetNodeTree(Root).OnValidate(node, data);
        }

        protected virtual void OnClearing(ITree<T> tree)
        {
            if (_EventHandlerList != null)
            {
                var e = (EventHandler) _EventHandlerList[ClearingEventKey];
                if (e != null) e(tree, EventArgs.Empty);
            }
        }

        protected virtual void OnCleared(ITree<T> tree)
        {
            if (_EventHandlerList != null)
            {
                var e = (EventHandler) _EventHandlerList[ClearedEventKey];
                if (e != null) e(tree, EventArgs.Empty);
            }
        }

        protected virtual void OnSetting(INode<T> node, T data)
        {
            OnSettingCore(node, data, true);
        }

        protected virtual void OnSettingCore(INode<T> node, T data, bool raiseValidate)
        {
            if (_EventHandlerList != null)
            {
                var e = (EventHandler<NodeTreeDataEventArgs<T>>) _EventHandlerList[SettingEventKey];
                if (e != null) e(node, new NodeTreeDataEventArgs<T>(data));
            }

            if (!IsRoot) GetNodeTree(Root).OnSettingCore(node, data, false);

            if (raiseValidate) OnValidate(node, data);
        }

        protected virtual void OnSetDone(INode<T> node, T data)
        {
            OnSetDoneCore(node, data, true);
        }

        protected virtual void OnSetDoneCore(INode<T> node, T data, bool raiseValidate)
        {
            if (_EventHandlerList != null)
            {
                var e = (EventHandler<NodeTreeDataEventArgs<T>>) _EventHandlerList[SetDoneEventKey];
                if (e != null) e(node, new NodeTreeDataEventArgs<T>(data));
            }

            if (!IsRoot) GetNodeTree(Root).OnSetDoneCore(node, data, false);

            //			if ( raiseValidate ) OnValidate( Node, Data );
        }

        protected virtual void OnInserting(INode<T> oldNode, NodeTreeInsertOperation operation, INode<T> newNode)
        {
            OnInsertingCore(oldNode, operation, newNode, true);
        }

        protected virtual void OnInsertingCore(INode<T> oldNode, NodeTreeInsertOperation operation, INode<T> newNode, bool raiseValidate)
        {
            if (_EventHandlerList != null)
            {
                var e = (EventHandler<NodeTreeInsertEventArgs<T>>) _EventHandlerList[InsertingEventKey];
                if (e != null) e(oldNode, new NodeTreeInsertEventArgs<T>(operation, newNode));
            }

            if (!IsRoot) GetNodeTree(Root).OnInsertingCore(oldNode, operation, newNode, false);

            if (raiseValidate) OnValidate(oldNode, newNode.Data);

            if (raiseValidate) OnInsertingTree(newNode);
        }

        protected virtual void OnInsertingTree(INode<T> newNode)
        {
            for (INode<T> child = newNode.Child; child != null; child = child.Next)
            {
                OnInsertingTree(newNode, child);

                OnInsertingTree(child);
            }
        }

        protected virtual void OnInsertingTree(INode<T> newNode, INode<T> child)
        {
            OnInsertingTreeCore(newNode, child, true);
        }

        protected virtual void OnInsertingTreeCore(INode<T> newNode, INode<T> child, bool raiseValidate)
        {
            if (_EventHandlerList != null)
            {
                var e = (EventHandler<NodeTreeInsertEventArgs<T>>) _EventHandlerList[InsertingEventKey];
                if (e != null) e(newNode, new NodeTreeInsertEventArgs<T>(NodeTreeInsertOperation.Tree, child));
            }

            if (!IsRoot) GetNodeTree(Root).OnInsertingTreeCore(newNode, child, false);

            if (raiseValidate) OnValidate(newNode, child.Data);
        }

        protected virtual void OnInserted(INode<T> oldNode, NodeTreeInsertOperation operation, INode<T> newNode)
        {
            OnInsertedCore(oldNode, operation, newNode, true);
        }

        protected virtual void OnInsertedCore(INode<T> oldNode, NodeTreeInsertOperation operation, INode<T> newNode, bool raiseValidate)
        {
            if (_EventHandlerList != null)
            {
                var e = (EventHandler<NodeTreeInsertEventArgs<T>>) _EventHandlerList[InsertedEventKey];
                if (e != null) e(oldNode, new NodeTreeInsertEventArgs<T>(operation, newNode));
            }

            if (!IsRoot) GetNodeTree(Root).OnInsertedCore(oldNode, operation, newNode, false);

            //			if ( raiseValidate ) OnValidate( OldNode, NewNode.Data );

            if (raiseValidate) OnInsertedTree(newNode);
        }

        protected virtual void OnInsertedTree(INode<T> newNode)
        {
            for (INode<T> child = newNode.Child; child != null; child = child.Next)
            {
                OnInsertedTree(newNode, child);

                OnInsertedTree(child);
            }
        }

        protected virtual void OnInsertedTree(INode<T> newNode, INode<T> child)
        {
            OnInsertedTreeCore(newNode, child, true);
        }

        protected virtual void OnInsertedTreeCore(INode<T> newNode, INode<T> child, bool raiseValidate)
        {
            if (_EventHandlerList != null)
            {
                var e = (EventHandler<NodeTreeInsertEventArgs<T>>) _EventHandlerList[InsertedEventKey];
                if (e != null) e(newNode, new NodeTreeInsertEventArgs<T>(NodeTreeInsertOperation.Tree, child));
            }

            if (!IsRoot) GetNodeTree(Root).OnInsertedTreeCore(newNode, child, false);

            //			if ( raiseValidate ) OnValidate( newNode, child.Data );
        }

        protected virtual void OnCutting(INode<T> oldNode)
        {
            if (_EventHandlerList != null)
            {
                var e = (EventHandler) _EventHandlerList[CuttingEventKey];
                if (e != null) e(oldNode, EventArgs.Empty);
            }

            if (!IsRoot) GetNodeTree(Root).OnCutting(oldNode);
        }

        protected virtual void OnCutDone(INode<T> oldRoot, INode<T> oldNode)
        {
            if (_EventHandlerList != null)
            {
                var e = (EventHandler) _EventHandlerList[CutDoneEventKey];
                if (e != null) e(oldNode, EventArgs.Empty);
            }

            if (!IsTree) GetNodeTree(oldRoot).OnCutDone(oldRoot, oldNode);
        }

        protected virtual void OnCopying(INode<T> oldNode, INode<T> newNode)
        {
            OnCopyingCore(oldNode, newNode, true);
        }

        protected virtual void OnCopyingCore(INode<T> oldNode, INode<T> newNode, bool raiseValidate)
        {
            if (_EventHandlerList != null)
            {
                var e = (EventHandler<NodeTreeNodeEventArgs<T>>) _EventHandlerList[CopyingEventKey];
                if (e != null) e(oldNode, new NodeTreeNodeEventArgs<T>(newNode));
            }

            if (!IsRoot) GetNodeTree(Root).OnCopyingCore(oldNode, newNode, false);

            //			if ( raiseValidate ) OnValidate( oldNode, newNode.Data );
        }

        protected virtual void OnCopied(INode<T> oldNode, INode<T> newNode)
        {
            OnCopiedCore(oldNode, newNode, true);
        }

        protected virtual void OnCopiedCore(INode<T> oldNode, INode<T> newNode, bool raiseValidate)
        {
            if (_EventHandlerList != null)
            {
                var e = (EventHandler<NodeTreeNodeEventArgs<T>>) _EventHandlerList[CopiedEventKey];
                if (e != null) e(oldNode, new NodeTreeNodeEventArgs<T>(newNode));
            }

            if (!IsRoot) GetNodeTree(Root).OnCopiedCore(oldNode, newNode, false);

            //			if ( raiseValidate ) OnValidate( oldNode, newNode.Data );
        }

        protected virtual void OnDeepCopying(INode<T> oldNode, INode<T> newNode)
        {
            OnDeepCopyingCore(oldNode, newNode, true);
        }

        protected virtual void OnDeepCopyingCore(INode<T> oldNode, INode<T> newNode, bool raiseValidate)
        {
            if (_EventHandlerList != null)
            {
                var e = (EventHandler<NodeTreeNodeEventArgs<T>>) _EventHandlerList[DeepCopyingEventKey];
                if (e != null) e(oldNode, new NodeTreeNodeEventArgs<T>(newNode));
            }

            if (!IsRoot) GetNodeTree(Root).OnDeepCopyingCore(oldNode, newNode, false);

            //			if ( raiseValidate ) OnValidate( oldNode, newNode.Data );
        }

        protected virtual void OnDeepCopied(INode<T> oldNode, INode<T> newNode)
        {
            OnDeepCopiedCore(oldNode, newNode, true);
        }

        protected virtual void OnDeepCopiedCore(INode<T> oldNode, INode<T> newNode, bool raiseValidate)
        {
            if (_EventHandlerList != null)
            {
                var e = (EventHandler<NodeTreeNodeEventArgs<T>>) _EventHandlerList[DeepCopiedEventKey];
                if (e != null) e(oldNode, new NodeTreeNodeEventArgs<T>(newNode));
            }

            if (!IsRoot) GetNodeTree(Root).OnDeepCopiedCore(oldNode, newNode, false);

            //			if ( raiseValidate ) OnValidate( oldNode, newNode.Data );
        }

        #endregion

        #region Nested type: AllChildrenEnumerator

        private class AllChildrenEnumerator : BaseEnumerableCollectionPair
        {
            public AllChildrenEnumerator(NodeTree<T> root) : base(root)
            {
            }

            public override IEnumerableCollection<INode<T>> Nodes
            {
                get { return new NodesEnumerableCollection(Root); }
            }

            #region Nested type: NodesEnumerableCollection

            protected class NodesEnumerableCollection : BaseNodesEnumerableCollection
            {
                public NodesEnumerableCollection(NodeTree<T> root) : base(root)
                {
                }

                protected NodesEnumerableCollection(NodesEnumerableCollection o) : base(o.Root)
                {
                }

                protected override BaseNodesEnumerableCollection CreateCopy()
                {
                    return new NodesEnumerableCollection(this);
                }

                public override bool MoveNext()
                {
                    if (!base.MoveNext()) goto hell;

                    if (CurrentNode == null) throw new InvalidOperationException("Current is null");

                    if (CurrentNode.Child != null)
                    {
                        CurrentNode = CurrentNode.Child;
                        return true;
                    }

                    for (; CurrentNode.Parent != null; CurrentNode = CurrentNode.Parent)
                    {
                        if (CurrentNode == Root) goto hell;
                        if (CurrentNode.Next != null)
                        {
                            CurrentNode = CurrentNode.Next;
                            return true;
                        }
                    }

                    hell:

                    AfterLast = true;
                    return false;
                }
            }

            #endregion
        }

        #endregion

        #region Nested type: AllEnumerator

        protected class AllEnumerator : BaseEnumerableCollectionPair
        {
            public AllEnumerator(NodeTree<T> root) : base(root)
            {
            }

            public override IEnumerableCollection<INode<T>> Nodes
            {
                get { return new NodesEnumerableCollection(Root); }
            }

            #region Nested type: NodesEnumerableCollection

            protected class NodesEnumerableCollection : BaseNodesEnumerableCollection
            {
                private bool _First = true;

                public NodesEnumerableCollection(NodeTree<T> root) : base(root)
                {
                }

                protected NodesEnumerableCollection(NodesEnumerableCollection o) : base(o.Root)
                {
                }

                protected override BaseNodesEnumerableCollection CreateCopy()
                {
                    return new NodesEnumerableCollection(this);
                }

                public override void Reset()
                {
                    base.Reset();

                    _First = true;
                }

                public override bool MoveNext()
                {
                    if (!base.MoveNext()) goto hell;

                    if (CurrentNode == null) throw new InvalidOperationException("Current is null");

                    if (CurrentNode.IsRoot)
                    {
                        CurrentNode = CurrentNode.Child;
                        if (CurrentNode == null) goto hell;
                    }

                    if (_First)
                    {
                        _First = false;
                        return true;
                    }

                    if (CurrentNode.Child != null)
                    {
                        CurrentNode = CurrentNode.Child;
                        return true;
                    }

                    for (; CurrentNode.Parent != null; CurrentNode = CurrentNode.Parent)
                    {
                        if (CurrentNode == Root) goto hell;
                        if (CurrentNode.Next != null)
                        {
                            CurrentNode = CurrentNode.Next;
                            return true;
                        }
                    }

                    hell:

                    AfterLast = true;
                    return false;
                }
            }

            #endregion
        }

        #endregion

        #region Nested type: BaseEnumerableCollectionPair

        protected abstract class BaseEnumerableCollectionPair : IEnumerableCollectionPair<T>
        {
            private NodeTree<T> _Root;

            protected BaseEnumerableCollectionPair(NodeTree<T> root)
            {
                _Root = root;
            }

            protected NodeTree<T> Root
            {
                get { return _Root; }
                set { _Root = value; }
            }

            // Nodes

            #region IEnumerableCollectionPair<T> Members

            public abstract IEnumerableCollection<INode<T>> Nodes { get; }

            public virtual IEnumerableCollection<T> Values
            {
                get { return new ValuesEnumerableCollection(_Root.DataComparer, Nodes); }
            }

            #endregion

            #region Nested type: BaseNodesEnumerableCollection

            protected abstract class BaseNodesEnumerableCollection : IEnumerableCollection<INode<T>>, IEnumerator<INode<T>>
            {
                private readonly object _SyncRoot = new object();
                private readonly int _Version;
                private bool _AfterLast;
                private bool _BeforeFirst = true;
                private INode<T> _CurrentNode;

                private NodeTree<T> _Root;

                protected BaseNodesEnumerableCollection(NodeTree<T> root)
                {
                    _Root = root;
                    _CurrentNode = root;

                    _Version = _Root.Version;
                }

                protected NodeTree<T> Root
                {
                    get { return _Root; }
                    set { _Root = value; }
                }

                protected INode<T> CurrentNode
                {
                    get { return _CurrentNode; }
                    set { _CurrentNode = value; }
                }

                protected bool BeforeFirst
                {
                    get { return _BeforeFirst; }
                    set { _BeforeFirst = value; }
                }

                protected bool AfterLast
                {
                    get { return _AfterLast; }
                    set { _AfterLast = value; }
                }

                protected virtual bool HasChanged
                {
                    get { return _Root.HasChanged(_Version); }
                }

                #region IEnumerableCollection<INode<T>> Members

                IEnumerator IEnumerable.GetEnumerator()
                {
                    return GetEnumerator();
                }

                public virtual IEnumerator<INode<T>> GetEnumerator()
                {
                    return this;
                }

                public virtual int Count
                {
                    get
                    {
                        BaseNodesEnumerableCollection e = CreateCopy();

                        int i = 0;
                        foreach (var o in e) i++;
                        return i;
                    }
                }

                public virtual bool IsSynchronized
                {
                    get { return false; }
                }

                public virtual object SyncRoot
                {
                    get { return _SyncRoot; }
                }

                void ICollection.CopyTo(Array array, int index)
                {
                    if (array == null) throw new ArgumentNullException("array");
                    if (array.Rank > 1) throw new ArgumentException("array is multidimensional", "array");
                    if (index < 0) throw new ArgumentOutOfRangeException("index");

                    int count = Count;

                    if (count > 0)
                        if (index >= array.Length) throw new ArgumentException("index is out of bounds", "index");

                    if (index + count > array.Length) throw new ArgumentException("Not enough space in array", "array");

                    BaseNodesEnumerableCollection e = CreateCopy();

                    foreach (var n in e)
                        array.SetValue(n, index++);
                }

                public virtual bool Contains(INode<T> item)
                {
                    BaseNodesEnumerableCollection e = CreateCopy();

                    IEqualityComparer<INode<T>> comparer = EqualityComparer<INode<T>>.Default;

                    foreach (var n in e)
                        if (comparer.Equals(n, item))
                            return true;

                    return false;
                }

                #endregion

                #region IEnumerator<INode<T>> Members

                public void Dispose()
                {
                    Dispose(true);

                    GC.SuppressFinalize(this);
                }

                object IEnumerator.Current
                {
                    get { return Current; }
                }

                public virtual void Reset()
                {
                    if (HasChanged) throw new InvalidOperationException("Tree has been modified.");

                    _CurrentNode = _Root;

                    _BeforeFirst = true;
                    _AfterLast = false;
                }

                public virtual bool MoveNext()
                {
                    if (HasChanged) throw new InvalidOperationException("Tree has been modified.");

                    _BeforeFirst = false;

                    return true;
                }

                public virtual INode<T> Current
                {
                    get
                    {
                        if (_BeforeFirst) throw new InvalidOperationException("Enumeration has not started.");
                        if (_AfterLast) throw new InvalidOperationException("Enumeration has finished.");

                        return _CurrentNode;
                    }
                }

                #endregion

                ~BaseNodesEnumerableCollection()
                {
                    Dispose(false);
                }

                protected abstract BaseNodesEnumerableCollection CreateCopy();

                protected virtual void Dispose(bool disposing)
                {
                }

                public virtual void CopyTo(T[] array, int index)
                {
                    ((ICollection) this).CopyTo(array, index);
                }
            }

            #endregion

            #region Nested type: ValuesEnumerableCollection

            private sealed class ValuesEnumerableCollection : IEnumerableCollection<T>, IEnumerator<T>
            {
                private readonly IEqualityComparer<T> _DataComparer;
                private readonly IEnumerator<INode<T>> _Enumerator;
                private readonly IEnumerableCollection<INode<T>> _Nodes;

                public ValuesEnumerableCollection(IEqualityComparer<T> dataComparer, IEnumerableCollection<INode<T>> nodes)
                {
                    _DataComparer = dataComparer;
                    _Nodes = nodes;
                    _Enumerator = _Nodes.GetEnumerator();
                }

                private ValuesEnumerableCollection(ValuesEnumerableCollection o)
                {
                    _Nodes = o._Nodes;
                    _Enumerator = _Nodes.GetEnumerator();
                }

                #region IEnumerableCollection<T> Members

                IEnumerator IEnumerable.GetEnumerator()
                {
                    return GetEnumerator();
                }

                public IEnumerator<T> GetEnumerator()
                {
                    return this;
                }

                public int Count
                {
                    get { return _Nodes.Count; }
                }

                public bool IsSynchronized
                {
                    get { return false; }
                }

                public object SyncRoot
                {
                    get { return _Nodes.SyncRoot; }
                }

                public void CopyTo(Array array, int index)
                {
                    if (array == null) throw new ArgumentNullException("array");
                    if (array.Rank > 1) throw new ArgumentException("array is multidimensional", "array");
                    if (index < 0) throw new ArgumentOutOfRangeException("index");

                    int count = Count;

                    if (count > 0)
                        if (index >= array.Length) throw new ArgumentException("index is out of bounds", "index");

                    if (index + count > array.Length) throw new ArgumentException("Not enough space in array", "array");

                    ValuesEnumerableCollection e = CreateCopy();

                    foreach (T n in e)
                        array.SetValue(n, index++);
                }

                public bool Contains(T item)
                {
                    ValuesEnumerableCollection e = CreateCopy();

                    foreach (T n in e)
                        if (_DataComparer.Equals(n, item))
                            return true;

                    return false;
                }

                #endregion

                #region IEnumerator<T> Members

                public void Dispose()
                {
                    Dispose(true);

                    GC.SuppressFinalize(this);
                }

                object IEnumerator.Current
                {
                    get { return Current; }
                }

                public void Reset()
                {
                    _Enumerator.Reset();
                }

                public bool MoveNext()
                {
                    return _Enumerator.MoveNext();
                }

                public T Current
                {
                    get
                    {
                        if (_Enumerator == null)
                        {
                            Debug.Assert(false);
                            return default(T);
                        }
                        if (_Enumerator.Current == null)
                        {
                            Debug.Assert(false);
                            return default(T);
                        }

                        return _Enumerator.Current.Data;
                    }
                }

                #endregion

                private ValuesEnumerableCollection CreateCopy()
                {
                    return new ValuesEnumerableCollection(this);
                }

                ~ValuesEnumerableCollection()
                {
                    Dispose(false);
                }

                private void Dispose(bool disposing)
                {
                }
            }

            #endregion
        }

        #endregion

        #region Nested type: DirectChildrenEnumerator

        private class DirectChildrenEnumerator : BaseEnumerableCollectionPair
        {
            public DirectChildrenEnumerator(NodeTree<T> root) : base(root)
            {
            }

            public override IEnumerableCollection<INode<T>> Nodes
            {
                get { return new NodesEnumerableCollection(Root); }
            }

            #region Nested type: NodesEnumerableCollection

            protected class NodesEnumerableCollection : BaseNodesEnumerableCollection
            {
                public NodesEnumerableCollection(NodeTree<T> root) : base(root)
                {
                }

                protected NodesEnumerableCollection(NodesEnumerableCollection o) : base(o.Root)
                {
                }

                public override int Count
                {
                    get { return Root.DirectChildCount; }
                }

                protected override BaseNodesEnumerableCollection CreateCopy()
                {
                    return new NodesEnumerableCollection(this);
                }

                public override bool MoveNext()
                {
                    if (!base.MoveNext()) goto hell;

                    if (CurrentNode == null) throw new InvalidOperationException("Current is null");

                    if (CurrentNode == Root)
                        CurrentNode = Root.Child;
                    else
                        CurrentNode = CurrentNode.Next;

                    if (CurrentNode != null) return true;

                    hell:

                    AfterLast = true;
                    return false;
                }
            }

            #endregion
        }

        #endregion

        #region Nested type: DirectChildrenInReverseEnumerator

        private class DirectChildrenInReverseEnumerator : BaseEnumerableCollectionPair
        {
            public DirectChildrenInReverseEnumerator(NodeTree<T> root) : base(root)
            {
            }

            public override IEnumerableCollection<INode<T>> Nodes
            {
                get { return new NodesEnumerableCollection(Root); }
            }

            #region Nested type: NodesEnumerableCollection

            protected class NodesEnumerableCollection : BaseNodesEnumerableCollection
            {
                public NodesEnumerableCollection(NodeTree<T> root) : base(root)
                {
                }

                protected NodesEnumerableCollection(NodesEnumerableCollection o) : base(o.Root)
                {
                }

                public override int Count
                {
                    get { return Root.DirectChildCount; }
                }

                protected override BaseNodesEnumerableCollection CreateCopy()
                {
                    return new NodesEnumerableCollection(this);
                }

                public override bool MoveNext()
                {
                    if (!base.MoveNext()) goto hell;

                    if (CurrentNode == null) throw new InvalidOperationException("Current is null");

                    if (CurrentNode == Root)
                        CurrentNode = Root.LastChild;
                    else
                        CurrentNode = CurrentNode.Previous;

                    if (CurrentNode != null) return true;

                    hell:

                    AfterLast = true;
                    return false;
                }
            }

            #endregion
        }

        #endregion

        #region Nested type: NodeXmlSerializationAdapter

        [XmlType("Node")]
        public class NodeXmlSerializationAdapter
        {
            private readonly IXmlCollection _Children = new ChildCollection();
            private readonly INode<T> _Node;
            private int _Version;

            private NodeXmlSerializationAdapter()
            {
                _Node = NewNode();
            }

            public NodeXmlSerializationAdapter(object tag, INode<T> node)
            {
                if (!ReferenceEquals(_XmlAdapterTag, tag)) throw new InvalidOperationException("Don't use this class");

                _Node = node;

                foreach (var child in node.DirectChildren.Nodes)
                    _Children.Add(new NodeXmlSerializationAdapter(_XmlAdapterTag, child));
            }

            [XmlAttribute]
            public int Version
            {
                get { return 1; }
                set { _Version = value; }
            }

            [XmlIgnore]
            public INode<T> Node
            {
                get { return _Node; }
            }

            public T Data
            {
                get { return _Node.Data; }

                set { GetNodeTree(_Node)._Data = value; }
            }

            public IXmlCollection Children
            {
                get { return _Children; }
                set { Debug.Assert(value == null); }
            }

            #region Nested type: ChildCollection

            private class ChildCollection : List<NodeXmlSerializationAdapter>, IXmlCollection
            {
            }

            #endregion

            #region Nested type: IXmlCollection

            public interface IXmlCollection : ICollection
            {
                NodeXmlSerializationAdapter this[int index] { get; }

                void Add(NodeXmlSerializationAdapter item);
            }

            #endregion
        }

        #endregion

        #region Nested type: RootObject

        [Serializable]
        protected class RootObject : NodeTree<T>
        {
            private IEqualityComparer<T> _DataComparer;
            private int _Version;

            public RootObject()
            {
            }

            public RootObject(IEqualityComparer<T> dataComparer)
            {
                _DataComparer = dataComparer;
            }

            protected RootObject(SerializationInfo info, StreamingContext context)
                : base(info, context)
            {
                int iVersion = info.GetInt32("RootObjectVersion");
                if (iVersion != 1)
                    throw new SerializationException("Unknown version");
            }

            protected override int Version
            {
                get { return _Version; }
                set { _Version = value; }
            }

            public override IEqualityComparer<T> DataComparer
            {
                get { return _DataComparer ?? (_DataComparer = EqualityComparer<T>.Default); }
                set { _DataComparer = value; }
            }

            [SecurityPermission(SecurityAction.Demand, SerializationFormatter = true)]
            public override void GetObjectData(SerializationInfo info, StreamingContext context)
            {
                base.GetObjectData(info, context);
                info.AddValue("RootObjectVersion", 1);
            }
        }

        #endregion

        #region Nested type: TreeXmlSerializationAdapter

        [XmlType("Tree")]
        public class TreeXmlSerializationAdapter
        {
            private ITree<T> _Tree;
            private int _Version;

            private TreeXmlSerializationAdapter()
            {
            }

            public TreeXmlSerializationAdapter(object tag, ITree<T> tree)
            {
                if (!ReferenceEquals(_XmlAdapterTag, tag)) throw new InvalidOperationException("Don't use this class");

                _Tree = tree;
            }

            [XmlAttribute]
            public int Version
            {
                get { return 1; }
                set { _Version = value; }
            }

            [XmlIgnore]
            public ITree<T> Tree
            {
                get { return _Tree; }
            }

            public NodeXmlSerializationAdapter Root
            {
                get { return new NodeXmlSerializationAdapter(_XmlAdapterTag, _Tree.Root); }

                set
                {
                    _Tree = NewTree();

                    ReformTree(_Tree.Root, value);
                }
            }

            private void ReformTree(INode<T> parent, NodeXmlSerializationAdapter node)
            {
                foreach (NodeXmlSerializationAdapter child in node.Children)
                {
                    INode<T> n = parent.AddChild(child.Data);

                    ReformTree(n, child);
                }
            }
        }

        #endregion
    }
}